#include <stdio.h>
#include <stdlib.h>
//#include <windows.h>

typedef struct node
{
    int number;
    struct node *next;
};

void add(struct node *node, struct node *head); // 把节点按顺序加入链表。把 node 加入 head 为头节点的链表。
void freememory(struct node *rubbish);          // 释放以 rubbish 为头节点地址的链表
void printchain(struct node *head);             // 输入一个链表的头节点 head，输出它的所有节点的值
struct node *split(struct node *head);          //如书上所要求，分离 head 链表中的偶数，并返回新链表的头节点指针

int main()
{
    int round;
    struct node *numhead, *numnode;
    struct node *ehead;
    int input;
    numhead = (struct node *)malloc(sizeof(struct node));
    numhead->next = NULL;
    //printf("Please enter %d numbers\n", INPUTS);
    round = 0;
    while (scanf("%d", &input) != EOF)
    {
        numnode = (struct node *)malloc(sizeof(struct node));
        numnode->number = input;
        add(numnode, numhead);
        round++;
    }
    //printf("\nNumbers: \n");
    printchain(numhead);
    ehead = split(numhead);
    //printf("\nOdd numbers: \n");
    printchain(numhead);
    //printf("\nEven numbers: \n");
    printchain(ehead);
    //printf("\nFree odd numbers: \n");
    freememory(numhead);
    //printf("\nFree even numbers: \n");
    freememory(ehead);
    //system("pause");
    return 0;
}

void add(struct node *node, struct node *head)
{

    struct node *tmpnode;
    tmpnode = head;
    while (1)
    {
        node->next = tmpnode->next;
        if (tmpnode->next == NULL || node->number <= tmpnode->next->number)
        {
            tmpnode->next = node;
            break;
        }
        tmpnode = tmpnode->next;
    }
}

struct node *split(struct node *head)
{
    struct node *newhead;
    struct node *lastnode;
    struct node *tmpnode;
    struct node *tmpnode2;
    tmpnode = head;
    tmpnode2 = head;
    newhead = (struct node *)malloc(sizeof(struct node));
    newhead->next = NULL;
    lastnode = newhead;
    while (tmpnode->next != NULL)
    {
        tmpnode = tmpnode->next;
        if (!((tmpnode->number) & 1))
        {
            tmpnode2->next = tmpnode->next; //把旧链表的上一个节点的next改为下一个节点的地址
            lastnode->next = tmpnode;       //把新链表最后一个节点的 next 指向 tmpnode 存储的地址
            tmpnode = tmpnode2;             //把tmpnode存储的地址改为旧链表上一个节点的地址，这样在下一轮循环时tmpnode就会指向下一个节点的地址
            lastnode = lastnode->next;      //把lastnode指向的地址改为最后一个节点的地址
            lastnode->next = NULL;          //把lastnode的next改为NULL以标记最后一个节点
            continue;                       //直接开始下一个循环，否则对于接连出现偶数的情况就会少转移一次
        }
        tmpnode2 = tmpnode2->next;
    }
    return newhead;
}

void printchain(struct node *head)
{
    struct node *tmpnode;
    for (tmpnode = head; tmpnode->next != NULL; tmpnode = tmpnode->next)
    {
        printf("%d", tmpnode->next->number);
        if (tmpnode->next->next != NULL)
        {
            printf("->");
        }
    }
    printf("\n");
}

void freememory(struct node *rubbish)
{
    struct node *pointer;
    while (rubbish != NULL)
    {
        pointer = rubbish;
        rubbish = rubbish->next;
        //printf("Free memory: %p\n", pointer);
        free(pointer);
    }
}